package cn.yy.test;

import java.util.ArrayList;
import java.util.List;

public class MyHashMap<K ,V> implements MyMap<K, V> {

	//默认的数组长度1 << 4 为 16
	/**
	 * 位移运算计算方法
	 *	1 % 2 = 1
	 * 把结果反过来为1
	 * (java中，整数默认就是int类型,也就是32位) 
	 * 最后得 ：0000 0000 0000 0000 0000 0000 0000 0001  
	 * 然后将结果向左移动4位得到: 0000 0000 0000 0000 0000 0000 0001 0000
	 * 最后将二进制转为十进制得 ： 16
	 * * */
    private static int defaultLength = 1<<4;	
	
    //使用的数组的大小
    private volatile int useSize;
    
    //扩容因子不可太大不可太小
    /**
     * 太大会造成大量的遍历和判断 链表过多
     * 太小会造成空间不足够效率低
     * useSize/defaultLength >0.75 就应该扩容
     */
    private static double defaultAddSizeFactor =0.75;
    
    //定义map的enty数组
    private Entry<K ,V> [ ] table=null;
    
    //新的数组 扩容后的数组
    private Entry<K ,V> [ ] newTable=null;
    
    //门面模式
    public MyHashMap(){
    	this(defaultLength , defaultAddSizeFactor);
    }
	
	public MyHashMap(int length, double defaultAddSizeFactor) {
		if (length<0){
			throw new IllegalArgumentException("参数不可为负数"+length);
		}
		if (defaultAddSizeFactor <=0 || Double.isNaN(defaultAddSizeFactor)){
			throw new IllegalArgumentException("扩容标准必需大于0"+defaultAddSizeFactor);
		}
		this.defaultLength = length;
		this.defaultAddSizeFactor = defaultAddSizeFactor;
		table = new Entry[defaultLength];
	}

	public V put(K k, V v) {
		//如果使用的数组大小大于负载因子x数组默认长度就要扩容
		if (useSize > defaultAddSizeFactor * defaultLength){
			up2Size();//2倍扩容方法
		}
		//获取数组位置的方法
		int index = getIndex(k , table.length);
		Entry<K ,V> entry =table[ index];
		
		if (entry ==null){
			//存储在数组和链表中的数据结构对象
			table[index] =new Entry(k , v ,null);
			useSize++;
		}else if(entry !=null){
			table[index] =new Entry(k , v ,entry);
		}
		
		return table[index].getValue();
	}

	//寻找存或者取的位置
	private int getIndex(K k, int length) {
		int m=length-1;
		int index=hash(k.hashCode() & m);
		return index;
	}

	//hash算法 下面的数字是经过计算好来确定的
	private int hash(int hashCode) {
		hashCode=hashCode^((hashCode>>>20)^(hashCode>>>12));
		return hashCode^((hashCode>>>7)^(hashCode>>>4));
	}

	//扩容数组方法
	private void up2Size() { 
		newTable=new Entry[2*defaultLength];
		//把旧 的数组内容再次hash到新数组
		againHash(newTable);
	}

	private void againHash(MyHashMap<K, V>.Entry<K, V>[] newTable2) {
		//将所有的数据全部遍历出来,如果是链表就递归遍历 放在list中
		List<Entry<K ,V>> entryList=new ArrayList<MyHashMap<K ,V>.Entry<K ,V>>();
		//遍历旧的内容到entryList中
		for(int i=0;i<table.length;i++){
			if(table[i]==null){
				continue;
			}
			//继续找存到数组上的entry对象
			//进入这方法就证明数组该位置不为空 table[i]==entry!=null
			foundEntryByNext(table[i],entryList);
		}
		//设置entryList
		if(entryList.size()>0){
			defaultLength=2*defaultLength;
			for(Entry<K ,V> entry:entryList){
				//置空链表
				if(entry.next!=null){
					entry.next=null;
				}
				useSize=0;
				put(entry.getKey(),entry.getValue());
			}
		}
		
	}

	//这方法不存在entry==null因为上面已经判断处理了如果为空的做法
	private void foundEntryByNext(MyHashMap<K, V>.Entry<K, V> entry,
			List<MyHashMap<K, V>.Entry<K, V>> entryList) {
		if(entry.next!=null){
			entryList.add(entry);
			//递归不断的一层层取存key
			foundEntryByNext(entry.next, entryList);
		}else{
			//没有链表的情况下
			entryList.add(entry);
		}
		
	}

	public V get(K k) {
		int index=getIndex(k, table.length);
		if(table[index]==null){
			throw new NullPointerException();
		}
		//key存在的话
		return findValueByEqualKey(k , table[index]);
	}

	//不同key可能在同一个位置
	private V findValueByEqualKey(K k, MyHashMap<K, V>.Entry<K, V> entry) {
		if(k==entry.getKey() || k.equals(entry.getKey())){
			return entry.getValue();
			//是否在下面链表
		}else if(entry.next!=null){
			//循环一层层递归和传进来k一样的entry
			return findValueByEqualKey(k, entry.next);
		}
		return null;
	}

	//创建一个内部存储的对象类型
	class Entry<K ,V> implements MyMap.Entry<K, V>{
		//外界传进来的封装的双列数据key value
		 K k;
		 V v;
		 //指向被this挤压下去的Entry对象
		 Entry<K ,V> next;
		 
		 public Entry(K k, V v, Entry<K ,V> next){
			 this.k=k;
			 this.v=v;
			 this.next=next;
		 }

		public K getKey() {
			// TODO Auto-generated method stub
			return k;
		}

		public V getValue() {
			// TODO Auto-generated method stub
			return v;
		}
	}
	
}
